package org.example.sword2offer.primary;

/**
 * @author: lynn
 * @Descript: 给定一个整形数组arr，已知其中所有的值都是非负的，将这个数组看作一个容器，请返回容器能装多少水。
 *   https://leetcode-cn.com/problems/trapping-rain-water/
 *  leetcode 42 接雨水的问题
 * @date: 2021/6/16 20:36
 * @version: 1.0
 */
public class Q71_1_ArrayMostWater {
    public static void main(String[] args) {
        int[] arr={0,1,0,2,1,0,1,3,2,1,2,1};
        System.out.println(trap(arr));
    }
    //解题思路 https://www.bilibili.com/video/BV1HE411Z7By?from=search&seid=5009556942389603904
    //思路：先找到最高的柱子，然后分别从柱子的左向最高柱子和右到最高柱子，当前柱子比前一个柱子小说明能存水
    public static int trap(int[] height){  //leetcode 接雨水问题
        int result=0;int maxValue=-1;int maxAddr=0;
        for (int i = 0; i <height.length ; i++) {
            if (height[i]>=maxValue){
                maxValue=height[i];maxAddr=i;
            }
        }
        for (int left = 0; left < maxAddr ; left++) { //左办部分处理
            for (int i = left+1; i <=maxAddr ; i++) {
                if (height[i]<height[left]) result=result+height[left]-height[i];else left=i;
            }
        }
        for (int right = height.length-1; right >maxAddr ; right--) { //右半部分处理
            for (int i = right-1; i >=maxAddr ; i--) {
                if (height[i]<height[right]) result=result+height[right]-height[i];else right=i;
            }
        }
        return result;
    }
}
